package cc.rico.algorithm;

import org.apache.commons.lang3.ArrayUtils;

/**
 * @Author: Dell
 * @Date: 2018/12/11
 * @Description:归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] items = new int[] {23, 22, 5, 6, 90, 43, 90, 1, 67, 78, 92, 23, 34};
        PrintUtil.printArray(items);

        int[] sortUpItems = arraySpilit(items);
//        PrintUtil.printArray(sortUpItems);
//
//        int[] sortDownItems = sortDown(items);
//        PrintUtil.printArray(sortDownItems);

    }


    private static int[] arraySpilit(int[] items) {
        if(items.length == 1) {
            return items;
        }

        if(items.length == 2) {
            if(items[0] > items[1]) {
                int temp = items[1];
                items[1] = items[0];
                items[1] = temp;
            }

            return items;
        }

        int score = 2;
        int len = items.length;

        int[] firstArray = subArray(items, 0, len/score);
        int[] firstSortArray = arraySpilit(firstArray);

        firstSortArray = doSortUp(firstSortArray);
        PrintUtil.printArray(firstSortArray);

        int[] secondArray = subArray(items, len/score, len-len/score);
        int[] secondSortArray = arraySpilit(secondArray);

        secondSortArray = doSortUp(secondSortArray);
        PrintUtil.printArray(secondSortArray);

        int[] results = arrayMerge(firstSortArray, secondSortArray);
        PrintUtil.printArray(results);

        return items;
    }

    private static int[] subArray(int[] items, int start, int len) {
        int[] subArray = new int[len];
        for(int i=0; i<len; i++) {
            subArray[i] = items[start+i];
        }

        return subArray;
    }

    private static int[] doSortUp(int[] items) {
        if(ArrayUtils.isEmpty(items)) {
            return null;
        }

        if(items.length == 1) {
            return items;
        }

        for(int i=0; i<items.length; i++) {
            for(int j=1; j<items.length-i; j++) {
                if(items[j-1] > items[j]) {
                    int temp = items[j-1];
                    items[j-1] = items[j];
                    items[j] = temp;
                }
            }
        }

        return items;
    }

    private static int[] arrayMerge(int[] firstArray, int[] secondArray) {
        int len = firstArray.length + secondArray.length;
        int[] array = new int[len];

        int firstIndex = 0;
        int secondIndex = 0;

        int index = 0;
        while (index < len) {

            if(firstIndex == firstArray.length) {
                array[index] = secondArray[secondIndex];
                secondIndex++;

            } else if(secondIndex == secondArray.length) {
                array[index] = firstArray[firstIndex];
                firstIndex++;

            } else if(firstArray[firstIndex] < secondArray[secondIndex]) {
                array[index] = firstArray[firstIndex];
                firstIndex ++;

            } else {
                array[index] = secondArray[secondIndex];
                secondIndex ++;
            }

            index++;
        }

        return array;
    }

}
